package day0313

import "sort"

func threeSum(nums []int) (res [][]int) {
	n := len(nums)
	sort.Ints(nums)
	for i, first := range nums {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		j, k := i+1, n-1
		for j < k {
			if j > i+1 && nums[j] == nums[j-1] {
				k++
				continue
			}
			if k+1 < n-1 && nums[k] == nums[k+1] {
				j--
				continue
			}
			if first+nums[j]+nums[k] == 0 {
				res = append(res, []int{first, nums[j], nums[k]})
				j++
				k--
			} else if first+nums[j]+nums[k] > 0 {
				k--
			} else {
				j++
			}
		}
	}
	return
}
